Dynamic translators translate one sequence of instructions into another sequence of instructions which is executed. The second sequence of instructions are `native` instructions--they can be executed directly by the machine on which the translator is running (this `machine` may be hardware or this machine may be defined by software that is running on yet another machine with its own architecture). A dynamic translator can be designed to execute instructions for one machine architecture (i.e., one instruction set) on a machine of a different architecture (i.e., with a different instruction set). Alternatively, a dynamic translator can take instructions that are native to the machine on which the dynamic translator is running and operate on that instruction stream to produce an optimized instruction stream. Also, a dynamic translator can include both of these functions (translation from one architecture to another, and optimization).
Caching dynamic translators attempt to identify program hot spots (frequently executed portions of the program, such as certain loops) at runtime and use a code cache to store translations of those frequently executed portions. Subsequent execution of those portions can use the cached translations, thereby reducing the overhead of executing those portions of the program.
Code cache replacement is required when the code cache does not have enough space for the placement of a translation (termed an allocation request). A conventional replacement policy has been to evict (also termed flush or replace) translations in the entire code cache or a large sub-portion of the code cache and then allocate new translations. A large number of translations are flushed because the cost of replacement at a finer granularity, i.e., one translation at a time, is prohibitive. The implicit logic behind such a replacement strategy is reactive: replace only in reaction to a space shortage.
A problem with such an approach is the timing of the replacement. For example, the translator could be in the middle of constructing a working set when the code cache runs out of space and is forced to flush. The translator will then recommence creating the working set and will probably have to recreate some of the just-evicted translations.
Because a code cache flush has been viewed as a costly operation, code caches are often sized large enough so that replacement is not needed. In contrast, well-timed preemptive replacement can considerably reduce the cost of code cache flushing, reduce memory requirements, and have other desirable side effects.